#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 超时
class Solution {
public:
    void dfs(vector<int> nums,  vector<vector<int>> &ans, vector<int> &flag, vector<int> &cur){
        if (cur.size() == nums.size()) {
            ans.push_back(cur);
            return;
        }

        for (int i = 0; i < flag.size(); i++) {
            if (flag[i] == true) continue;

            // 如果前一个数字被加入到了cur，并且与当前数字相同，且当前数字没有被添加
            // 则不添加。
            if (i > 0 && !flag[i - 1] && nums[i] == nums[i - 1]) continue;

            if (flag[i] == false) {
                cur.push_back(nums[i]);
                flag[i] = true;
                dfs(nums, ans, flag, cur);
                // 还原现场
                cur.pop_back();
                flag[i] = false;
            }
        }
        return;
    }

    bool isSame(vector<int> a, vector<int> b) {
        if (a.size() != b.size()) return false;

        for (int i = 0; i < a.size(); i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }

    void nextPermutation(vector<int>& nums) {
        vector<int> arr = nums;
        // 排序
        sort(arr.begin(), arr.end());

        vector<vector<int>> ans;
        vector<int> flag(arr.size(), false);
        vector<int> cur;
        dfs(arr, ans, flag, cur);
        
        for (int i = 0; i < ans.size(); i++) {
            if (isSame(ans[i], nums) == true) {
                if (i + 1 == ans.size()) {
                    sort(nums.begin(), nums.end());
                    return;
                }
                for (int j = 0; j < nums.size(); j ++) {
                    nums[j] = ans[i + 1][j];
                }
                return;
            }
        }
    }
};